package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.function.BiFunction;
import java.util.function.BiPredicate;
import java.util.function.Function;

/**
 * @author feizns
 * @since 2020/3/9
 */
public class Rob {

    public static void main(String[] args) {

    }

    static Map<TreeNode, Integer> CACHE = new HashMap<>();

    public static int rob(TreeNode root) {
        Integer ret = CACHE.get(root);
        if ( ret != null )
            return ret;
        if ( root != null ) {
            int son = 0;
            int gSon = 0;
            if ( root.left != null ) {
                son += rob(root.left);
                gSon += rob(root.left.left);
                gSon += rob(root.left.right);
            }
            if ( root.right != null ) {
                son += rob(root.right);
                gSon += rob(root.right.left);
                gSon += rob(root.right.right);
            }
            int max = Math.max(root.val + gSon, son);
            CACHE.put(root, max);
        }
        return 0;
    }

    private static int sum(List<Integer> list, BiPredicate<Integer, Integer> predicate) {
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            Integer item = list.get(i);
            if ( predicate.test(i, item) )
                sum += item;
        }
        return sum;
    }

}
